package com.wangjw.interview.tree;

/**
 * Created by wangjw on 18/5/11.
 */
public class TreeTraversal {

    // 前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.getValue());
        preOrder(root.getLeft());
        preOrder(root.getRight());
    }

    // 中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        inOrder(root.getLeft());
        System.out.print(root.getValue());
        inOrder(root.getRight());
    }

    // 后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.print(root.getValue());
    }

    // 后序遍历
    public String postOrder(String preOrder, String inOrder) {
        if (preOrder.isEmpty()) {
            return "";
        }

        char rootValue = preOrder.charAt(0);
        int rootIndex = inOrder.indexOf(rootValue);

        return
                postOrder(
                        preOrder.substring(1, 1 + rootIndex),
                        inOrder.substring(0, rootIndex)) +
                postOrder(
                        preOrder.substring(1 + rootIndex),
                        inOrder.substring(1 + rootIndex)) +
                rootValue;
    }

    public static void main(String[] args) {
        TreeCreator creator = new TreeCreator();
        TreeTraversal treeTraversal = new TreeTraversal();

        System.out.println("========");
        System.out.println("Sample tree traversal");
        System.out.println("========");

        TreeNode sampleTree = creator.createSampleTree();
        treeTraversal.preOrder(sampleTree);
        System.out.println();
        treeTraversal.inOrder(sampleTree);
        System.out.println();
        treeTraversal.postOrder(sampleTree);
        System.out.println();

        System.out.println("\n========");
        System.out.println("Creating tree from preOrder and inOrder");
        System.out.println("========");

        TreeNode tree = creator.createTree("ABDEGCF", "DBGEACF");
        treeTraversal.postOrder(tree);
        System.out.println();
        treeTraversal.postOrder(creator.createTree("", ""));
        System.out.println();
        treeTraversal.postOrder(creator.createTree("A", "A"));
        System.out.println();
        treeTraversal.postOrder(creator.createTree("AB", "BA"));
        System.out.println();

        System.out.println("\n========");
        System.out.println("Generating postOrder directly");
        System.out.println("========");

        System.out.println(treeTraversal.postOrder("ABDEGCF", "DBGEACF"));
        System.out.println(treeTraversal.postOrder("", ""));
        System.out.println(treeTraversal.postOrder("A", "A"));
        System.out.println(treeTraversal.postOrder("AB", "BA"));
    }
}
